#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/// Definition for an interval.
struct Interval {
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

bool compare(const Interval &a, const Interval &b){

    if(a.start != b.start)
        return a.start < b.start;		// 谁起始点小 谁排在前面
    return a.end < b.end;				// 终止点靠前谁靠前
}

// 435: Non-overlapping Intervals  : 最少要删除多少个组合 【参考递增子序列】
// 时间复杂度: O(n^2) 空间复杂度: O(n)

class Solution {
public:
    int eraseOverlapIntervals(vector<Interval>& intervals) {
  		if(intervals.size() == 0){
			return 0;
		}  
		
		sort(intervals.begin(), intervals.end(), compare);	// 默认不支持比较,编写比较函数

		//  memo[i]表示以intervals[i]为结尾的区间能构成的最长不重叠区间序列
		vector<int> memo(intervals.size(), 1);
		for(int i = 1; i < intervals.size(); i++){
			// memo[i]
			for(int j = 0; j < i; j++){	// 第i个区间前面的区间,
				// 第i个区间初始值大于等于 第j个区间结尾，则第i个区间可以跟在第j个区间后面
				if(intervals[i].start >= intervals[j].end)
					memo[i] = max(memo[i], 1 + memo[j]);
			}
		}

		int res = 0;
		for(int i = 0;i < memo.size(); i++){
			res = max(res, memo[i]);
		}
		
		return intervals.size() - res;
    }
};

int main(){
	Interval interval1[] = {Interval(1,2), Interval(2,3), Interval(3,4), Interval(1,3)};
    vector<Interval> v1(interval1, interval1 + sizeof(interval1)/sizeof(Interval));
    cout << Solution().eraseOverlapIntervals(v1) << endl;

    Interval interval2[] = {Interval(1,2), Interval(1,2), Interval(1,2)};
    vector<Interval> v2(interval2, interval2 + sizeof(interval2)/sizeof(Interval));
    cout << Solution().eraseOverlapIntervals(v2) << endl;

    Interval interval3[] = {Interval(1,2), Interval(2,3)};
    vector<Interval> v3(interval3, interval3 + sizeof(interval3)/sizeof(Interval));
    cout << Solution().eraseOverlapIntervals(v3) << endl;

    return 0;
}
